Leetcode 309.最佳买卖股票时机含冷冻期

题目描述：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）。

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

1
2
3

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

链接：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

题目分析

  应该还是采用动态规划的方法，我们考虑一下每一天的状态，应该有三种：手中没有股票（不在冷冻期）、手中没有股票（在冷冻期）、手中持有股票。这是因为冷冻期一定是在卖出股票后才发生的，而我们不能同时参与多笔交易，那么冷冻期的时候手上一定没有股票。然后我们每一天能做出的选择只有买入、卖出或者不做任何事（当然，它们也有一定的前提），我们思考一下对于每种状态，做出选择后结果如何。

• 手中没有股票且不在冷冻期 nostock。这个时候我们可以买入股票或者保持不变。
  • 买入股票：手中的钱变为 nostock - prices[i]，同时状态变为持有股票。
  • 保持不变：手中的钱不变，状态也不变。
• 手中没有股票且在冷冻期 cooldown。这个时候我们只有保持不变一种选择。
  • 保持不变：手中的钱不变，状态变为了手中没有股票且不在冷冻期。
• 手中持有股票 havestock。这个时候我们可以卖出股票或者保持不变。
  • 卖出股票：手中的钱变为 havestock + prices[i]，同时状态变为冷冻期。
  • 保持不变：手中的钱不变，状态也不变。

  那么我们就得到状态转移的方式了，对于每种状态，不管是以何种状态转移过来的都没有影响（比如持有股票是本来就持有的还是昨天买入的并没有差别），那么我们只需要让该状态手中的钱尽可能地多就可以了。而且状态转移只与前一天的状态有关，那么我们也不需要一个数组来存放所有状态，我们只需要三个变量分别记录这三种状态。
  我们的初始资金可以定为 0，并允许资金为负的情况，这样最后得到的结果就是我们的利润。对于第 0 天的状态，只有买入或者不买入，我们就可以得到三种状态的初始值，之后从第 1 天开始进行状态转移即可。遍历数组后，我们比较两种手里没有股票的情况选择更大的就是答案（到结束时手里还持有股票一定不会是利润最大的情况）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int nostock = 0;
        int havestock = -prices[0];
        int cooldown = 0;
        for(int i = 1; i < prices.size(); i++){
            int newnostock = max(nostock, cooldown);
            int newhavestock = max(havestock, nostock - prices[i]);
            int newcooldown = havestock + prices[i];
            nostock = newnostock;
            havestock = newhavestock;
            cooldown = newcooldown;
        }
        return max(nostock, cooldown);
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们只需要遍历一次数组进行状态转移，并且每次状态转移的复杂度是 $O(1)$。
  空间复杂度：$O(1)$。我们只需要常数个变量记录状态。